home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / brklyprl.lha / Emulator / Tests / mu.pl < prev    next >
Encoding:
Text File  |  1989-04-14  |  3.3 KB  |  142 lines
  1.  
  2. /* Copyright (C) 1988, 1989 Herve' Touati, Aquarius Project, UC Berkeley */
  3.  
  4. %
  5. %    The MU-puzzle
  6. %        from Hofstadter's "Godel, Escher, Bach" (pp. 33-6).
  7. %
  8.  
  9. %    To find a derivation type, for example: 
  10. %        theorem(muiiu).
  11. %    Also try 'miiiii' (uses all rules) and 'muui' (requires 11 steps).
  12. %    Note that it can be shown that (# of i's) cannot be a multiple
  13. %    of three (which includes 0).
  14.  
  15. %    Some results:
  16. %
  17. %    string        # steps
  18. %    ------        -------
  19. %    mi        1
  20. %    mu        -
  21. %    mii        2
  22. %    miu        2
  23. %    mui        4
  24. %    muu        -
  25. %    miii        -
  26. %    miiu        3
  27. %    miui        8
  28. %    miuu        5
  29. %    muii        8
  30. %    muiu        5
  31. %    muui        11
  32. %    muuu        -
  33. %    miiii        3
  34. %    miiiu        -
  35. %    miiui        -
  36. %    miiuu        6
  37. %    miuii        -
  38. %    miuiu        3
  39. %    miuui        6
  40. %    miuuu        9
  41. %    muiii        -
  42. %    muiiu        6
  43. %    muiui        5
  44. %    muiuu        9
  45. %    muuii        6
  46. %    muuiu        9
  47. %    muuui        9
  48. %    muuuu        -
  49.  
  50. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  51. main :- theorem(muui).
  52.  
  53. % First break goal atom into a list of characters,
  54. % find the derivation, and then print the results.
  55. theorem(Goal) :-
  56.     explode(Goal, G),
  57.     length(G, GL1),
  58.     GL is GL1 - 1,
  59.     derive([m,i], G, 1, GL, Derivation, 0),
  60.     nl, print_results([rule(0,[m,i])|Derivation], 0).
  61.  
  62. % derive(StartString, GoalString, StartStringLength, GoalStringLength,
  63. %        Derivation, InitBound).
  64. derive(S, G, SL, GL, D, B) :- 
  65.     B1 is B + 1,
  66.     write('depth '), write(B1), nl,
  67.     derive2(S, G, SL, GL, 1, D, B).
  68. derive(S, G, SL, GL, D, B) :- 
  69.     B1 is B + 1,
  70.     derive(S, G, SL, GL, D, B1).
  71.  
  72. % derive2(StartString, GoalString, StartStringLength, GoalStringLength,
  73. %        ScanPointer, Derivation, NumRemainingSteps).
  74. derive2(S, S, SL, SL, _,   [], _).
  75. derive2(S, G, SL, GL, Pin, [rule(N,I)|D], R) :-
  76.     lower_bound(SL, GL, B),
  77.     R >= B,
  78.     R1 is R - 1,
  79.     rule(S, I, SL, IL, Pin, Pout, N),
  80.     derive2(I, G, IL, GL, Pout, D, R1).
  81.  
  82. rule([m|T1], [m|T2], L1, L2, Pin, Pout, N) :-
  83.     rule(T1, T2, L1, L2, Pin, Pout, 1, i, N, X-X).
  84.  
  85. % rule(InitialString, FinalString, InitStrLength, FinStrLength,
  86. %        ScanPtrIn, ScanPtrOut, StrPosition, PreviousChar,
  87. %        RuleNumber, DifferenceList).
  88. %   The difference list is used for doing a list concatenate in rule 2.
  89. rule([i],       [i,u],  L1, L2, Pin, Pout, Pos, _, 1, _) :- 
  90.                             Pos >= Pin,
  91.                             Pout is Pos - 2,
  92.                             L2 is L1 + 1.
  93. rule([],        L,      L1, L2, _,   1,    _,   _, 2, L-[]) :-
  94.                             L2 is L1 + L1.
  95. rule([i,i,i|T], [u|T],  L1, L2, Pin, Pout, Pos, _, 3, _) :- 
  96.                             Pos >= Pin,
  97.                             Pout is Pos - 1,
  98.                             L2 is L1 - 2.
  99. rule([u,u|T],   T,      L1, L2, Pin, Pout, Pos, i, 4, _) :-
  100.                             Pos >= Pin,
  101.                             Pout is Pos - 2,
  102.                             L2 is L1 - 2.
  103. rule([H|T1],    [H|T2], L1, L2, Pin, Pout, Pos, _, N, L-[H|X]) :-
  104.     Pos1 is Pos + 1,
  105.     rule(T1,  T2,  L1, L2, Pin, Pout, Pos1, H, N, L-X).
  106.  
  107. print_results([], _).
  108. print_results([rule(N,G)|T], M) :-
  109.     M1 is M + 1,
  110.     implode(A, G),
  111.     write(M1), write('  '), print_rule(N), write(A), nl,
  112.     print_results(T, M1).
  113.  
  114. print_rule(0) :- write('axiom    ').
  115. print_rule(N) :- N =\= 0, write('rule '), write(N), write('   ').
  116.  
  117. % Break atom A into list of characters L.
  118. explode(A, L) :-
  119.     name(A, Ascii),
  120.     name_list(L, Ascii).
  121.  
  122. % Combine list of characters L into atom A.
  123. implode(A, L) :-
  124.     name_list(L, Ascii),
  125.     name(A, Ascii).
  126.  
  127. name_list([], []).
  128. name_list([H1|T1], [H2|T2]) :-
  129.     name(H1, [H2]),
  130.     name_list(T1, T2).
  131.  
  132. lower_bound(N, M, 1) :- N < M.
  133. lower_bound(N, N, 2).
  134. lower_bound(N, M, B) :-
  135.     N > M,
  136.     Diff is N - M,
  137.     (even(Diff) ->
  138.         B is Diff // 2;
  139.         B is (Diff + 1) // 2 + 1).
  140.     
  141. even(N) :- 0 is (N mod 2).
  142.